import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class LeetCode904 {
    public int totalFruit(int[] fruits) {
        int len = 1;
        HashSet<Integer> set = new HashSet<>();
        int n = fruits.length;
        for (int i = 0; i < n - 1; i++) {
            set.add(fruits[i]);
            set.add(fruits[i + 1]);
            int j = i + 2;
            for (; j < n; j++) {
                if (set.size() < 2 || set.size() == 2 && set.contains(fruits[j])) {
                    set.add(fruits[j]);
                } else {
                    break;
                }
            }
            len = Math.max(len, j - i);
            set.clear();
        }
        return len;
    }

    public static void main(String[] args) {
        System.out.println(totalFruit2(new int[]{3,3,3,1,2,1,1,2,3,3,4}));
    }

    public static int totalFruit2(int[] f) {
        int n = f.length;
        int left = 0;
        int right = 0;
        Map<Integer, Integer> hashMap = new HashMap<>();
        int len = 0;
        while (right < n) {
            hashMap.put(f[right], hashMap.getOrDefault(f[right], 0) + 1);
            right++;
            while (hashMap.size() > 2) {
                int num = f[left];
                hashMap.put(num, hashMap.get(num) - 1);
                left++;
                if (hashMap.get(num) == 0) {
                    hashMap.remove(num);
                    break;
                }
            }
            len = Math.max(len, right - left);
        }
        return len;
    }

    public int totalFruit3(int[] f) {//使用数组替换哈希表
        int n = f.length;
        int left = 0;
        int right = 0;
        // Map<Integer, Integer> hashMap = new HashMap<>();
        int[] arr = new int[n];
        int kinds = 0;
        int len = 0;
        while (right < n) {
            if (arr[f[right]] == 0) {
                kinds++;
            }
            arr[f[right++]]++;
            // right++;
            while (kinds > 2) {
                int num = f[left++];
                arr[num]--;
                // left++;
                if (arr[num] == 0) {
                    kinds--;
                    break;
                }
            }
            len = Math.max(len, right - left);
        }
        return len;
    }
}
